import java.util.ArrayList;
import java.util.List;

/*
 * @author zzr
 * @date: 2025/10/15  23:55
 * @description: 前序遍历
 */
public class Demo19 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        ret.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        ret.addAll(leftTree);

        List<Integer> rightTree = preorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }


    /**
     * 获取二叉树元素个数
     * @param root
     * @return
     */
    public int nodeSize(TreeNode root) {
        int size = 0;
        if (root == null) return size;

        int leftSize = nodeSize(root.left);
        int rightSize = nodeSize(root.right);

        return leftSize + rightSize + 1;
    }

    int leaveSize;
    public int getLeaveSize(TreeNode root) {
        if (root == null) return leaveSize;
        if (root.left == null && root.right == null) {
            leaveSize++;
        }
        getLeaveSize(root.left);
        getLeaveSize(root.right);
        return leaveSize;
    }

    /**
     * 获得第 K 层的节点的个数
     * @param root
     * @return
     */
    public int getKLeaveNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) {
            return 1;
        }
        return getKLeaveNodeCount(root.left, k - 1) + getKLeaveNodeCount(root.right, k - 1);
     }

     /**
      * 得到树的高度
      */
     public int getTreeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftTreeHeight = getTreeHeight(root.left);
        int rightTreeHeight = getTreeHeight(root.right);

        return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
     }

    /**
     * 查二叉树是否存在值为val的元素
     * @param root
     * @param val
     * @return
     */
     public boolean find(TreeNode root, char val) {
         if (root == null)
             return false;
         if (root.val == val) {
             return true;
         }
         boolean leftFlg = find(root.left,val);
         if (leftFlg == true) {
             return true;
         }
         boolean rightFlg = find(root.right,val);
         if (rightFlg == true) {
             return true;
         }
         return false;
     }
}
